package algorithmExample.divideandconquer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: zhangrongqing
 * @Date: 2019/11/15 15:26
 */
//题目：https://leetcode-cn.com/problems/the-skyline-problem/
public class SkylineProblem {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        int length = buildings.length;
        List<List<Integer>> output = new ArrayList<>(new ArrayList<>());
        if (length == 1) {
            List list1 = new ArrayList();
            list1.add(buildings[0][0]);
            list1.add(buildings[0][2]);
            List list2 = new ArrayList();
            list2.add(buildings[0][1]);
            list2.add(0);

            output.add(list1);
            output.add(list2);
            return output;
        }
        List<List<Integer>> leftSkyBuilding = getSkyline(Arrays.copyOfRange(buildings, 0, length / 2));
        List<List<Integer>> rightBuilding = getSkyline(Arrays.copyOfRange(buildings, length / 2, length));

        return mergeSkyline(leftSkyBuilding, rightBuilding);
    }

    public List<List<Integer>> mergeSkyline(List<List<Integer>> list1, List<List<Integer>> list2) {
        int leftpos = 0, rightpos = 0, hight = 0;
        List<List<Integer>> output = new ArrayList<>(new ArrayList<>());
        while (leftpos < list1.size() && rightpos < list2.size()) {
            if (list1.get(leftpos).get(0) > list2.get(rightpos).get(0)) {
                leftpos++;
                if (list1.get(leftpos).get(1) > hight) {
                    output.add(list1.get(leftpos));
                }
            } else {
                rightpos++;
            }

        }
        output.addAll(list1.size() == leftpos ? list2.subList(rightpos, list2.size()) : list1.subList(leftpos, list1.size()));
        return output;
    }

    public static void main(String[] args) {

    }
}
